package BinaryTree;

import org.junit.Test;

/*
    每个节点只处理自己（单cur思想）
    做完题一定写入表格
*/
public class 二叉搜索树与双向链表简指36 {
    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }

    };
    
    @Test
    public void test() {

        Node n4 = new Node(4);
        Node n2 = new Node(2);
        Node n5 = new Node(5);
        Node n1 = new Node(1);
        Node n3 = new Node(3);
        n4.left=n2;n4.right=n5;
        n2.left=n1;n2.right=n3;

        Node node = back(n4);
        node.left=fir;
        fir.right=node;
//        Node t=null;
//        System.out.println("---");
//        while(node!=null){
//            System.out.println(node.val);
//            t= node;
//            node = node.left;
//        }
//        while(t!=null){
//            System.out.println(t.val);
//            t= t.right;
//        }
    }
    int f=0;
    Node fir=null;
    public Node back(Node root) {
        if(root==null)return null;
        if(root.left==null && root.right==null){
            if(f==0) {
                f++;
                fir = root;
            }
            return root;
        }

        Node son = back(root.left);
        root.left = son;
        son.right=root;

        Node sonR = back(root.right);
        sonR.left=root;
        root.right = sonR;

        return root.right;
    }
}
